package com.tianyuan.test3;
import java.util.*;
/**
 * 有效括号序列
 *
 * @date 2025/10/18 22:46
 * 给出一个仅包含字符仅由括号字符'['、']'、'('、')'、'{'、'}'的括号序列字符串 s (0≤|s|≤10的4次方），
 * 你需要判断给出的括号序列字符串s是否是有效的括号序列。
 *
 * 有效括号序列的定义如下：
 * ●空序列是有效括号序列；
 * ●如果A是有效括号序列，则(A)、[A]和A都是有效括号序列；
 * ●如果A和B都是有效括号序列，则它们的拼接AB也是有效括号序列。
 * 如果括号序列字符串s是有效的括号序列，返回一个布尔值true；否则返回一个布尔值false。
 *
 * 输入："["   返回值：false
 * 输入："[]"   返回值：true
 */

public class Solution {

    /**
     * 判断括号序列是否有效
     * @param s 输入的括号字符串（仅包含()[]{}）
     * @return 有效返回true，否则返回false
     */
    public boolean isValid (String s) {
        // 栈用于存储未匹配的开括号（左括号），后续通过栈顶元素匹配闭括号（右括号）
        Stack<Character> stack = new Stack<>();

        // 遍历字符串中的每个字符
        for (char c : s.toCharArray()) {
            // 情况1：当前字符是开括号（左括号），直接压入栈中等待匹配
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            // 情况2：当前字符是闭括号（右括号），需要与栈顶的开括号匹配
            else if (c == ')' || c == ']' || c == '}') {
                // 若栈为空（没有开括号可匹配），或栈顶开括号与当前闭括号不匹配，直接返回无效
                if (stack.isEmpty() || !isMatchingPair(stack.peek(), c)) {
                    return false;
                }
                // 若匹配成功，弹出栈顶的开括号（已完成匹配，无需保留）
                stack.pop();
            }
        }

        // 遍历结束后，若栈为空，说明所有开括号都已匹配；否则存在未匹配的开括号，无效
        return stack.isEmpty();
    }

    /**
     * 检查一对开括号和闭括号是否匹配（如'('与')'匹配）
     * @param open 开括号（左括号）
     * @param close 闭括号（右括号）
     * @return 匹配返回true，否则返回false
     */
    private static boolean isMatchingPair(char open, char close) {
        // 严格匹配三种括号对
        return (open == '(' && close == ')') ||
                (open == '[' && close == ']') ||
                (open == '{' && close == '}');
    }










    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例1：输入"["
        String test1 = "[";
        boolean result1 = solution.isValid(test1);
        System.out.println("输入：\"[\"  返回值：" + result1);  // 预期输出：false

        // 测试用例2：输入"[]"
        String test2 = "[]";
        boolean result2 = solution.isValid(test2);
        System.out.println("输入：\"[]\"  返回值：" + result2);  // 预期输出：true


        String test3 = "A";
        boolean result3 = solution.isValid(test3);
        System.out.println("输入：\"A\"  返回值：" + result3);

    }
}